package backtracking;
/**
 * 
 * @author victor
 * 
 */
public class Mochila2Backtracking {

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] ps = new int[] { 3, 6, 9, 5 };
		int[] bs = new int[] { 7, 2, 10, 4 };
		mochila_0_1(ps, bs, 15);
	}

	/**
	 * 
	 * @param ps
	 * @param bs
	 * @param c
	 * @return
	 */
	private static int mochila_0_1(int[] ps, int[] bs, int c) {
		int[] solParcial = new int[ps.length];
		int[] solOptima = new int[ps.length];
		int bOpt = buscar01(ps.length, 0, c, 0, solParcial, solOptima, -1, ps, bs, c);
		imprimir(solOptima, bOpt);
		return bOpt;
	}

	/**
	 * 
	 * @param v
	 * @param bOpt
	 */
	private static void imprimir(int[] v, int bOpt) {
		for (int i = 0; i < v.length; i++)
			System.out.print(v[i] + " ");
		System.out.println("= " + bOpt);
	}

	/**
	 * 
	 * @param n
	 * @param i
	 * @param p
	 * @param b
	 * @param solParc
	 * @param solOpt
	 * @param bOpt
	 * @param ps
	 * @param bs
	 * @param c
	 * @return
	 */
	private static int buscar01(int n, int i, int p, int b, int[] solParc, int[] solOpt, int bOpt, int[] ps, int[] bs, int c) {
		for (int k = 0; k <= 1; k++) {
			if (k * ps[i] <= p) {
				solParc[i] = k;
				int np = p - k * ps[i];
				int nb = b + k * bs[i];
				if (i == n - 1) {
					if (nb > bOpt) {
						bOpt = nb;
						for (int j = 0; j < ps.length; j++)
							solOpt[j] = solParc[j];
					}
				} else
					bOpt = buscar01(n, i + 1, np, nb, solParc, solOpt, bOpt, ps, bs, c);
				// int np = p + k*ps[i]; innecesaria
				// int nb = b - k*bs[i]; innecesaria
			}
		}
		return bOpt;
	}

}
